{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #The Number of Weak Characters in the Game"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #stack #greedy #array #sorting #monotonic-stack"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #栈 #贪心 #数组 #排序 #单调栈"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: numberOfWeakCharacters"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #游戏中弱角色的数量"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>你正在参加一个多角色游戏，每个角色都有两个主要属性：<strong>攻击</strong> 和 <strong>防御</strong> 。给你一个二维整数数组 <code>properties</code> ，其中 <code>properties[i] = [attack<sub>i</sub>, defense<sub>i</sub>]</code> 表示游戏中第 <code>i</code> 个角色的属性。</p>\n",
    "\n",
    "<p>如果存在一个其他角色的攻击和防御等级 <strong>都严格高于</strong> 该角色的攻击和防御等级，则认为该角色为 <strong>弱角色</strong> 。更正式地，如果认为角色 <code>i</code> <strong>弱于</strong> 存在的另一个角色 <code>j</code> ，那么 <code>attack<sub>j</sub> &gt; attack<sub>i</sub></code> 且 <code>defense<sub>j</sub> &gt; defense<sub>i</sub></code> 。</p>\n",
    "\n",
    "<p>返回 <strong>弱角色</strong> 的数量。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>properties = [[5,5],[6,3],[3,6]]\n",
    "<strong>输出：</strong>0\n",
    "<strong>解释：</strong>不存在攻击和防御都严格高于其他角色的角色。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>properties = [[2,2],[3,3]]\n",
    "<strong>输出：</strong>1\n",
    "<strong>解释：</strong>第一个角色是弱角色，因为第二个角色的攻击和防御严格大于该角色。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>properties = [[1,5],[10,4],[4,3]]\n",
    "<strong>输出：</strong>1\n",
    "<strong>解释：</strong>第三个角色是弱角色，因为第二个角色的攻击和防御严格大于该角色。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>2 &lt;= properties.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>properties[i].length == 2</code></li>\n",
    "\t<li><code>1 &lt;= attack<sub>i</sub>, defense<sub>i</sub> &lt;= 10<sup>5</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [the-number-of-weak-characters-in-the-game](https://leetcode.cn/problems/the-number-of-weak-characters-in-the-game/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [the-number-of-weak-characters-in-the-game](https://leetcode.cn/problems/the-number-of-weak-characters-in-the-game/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[5,5],[6,3],[3,6]]', '[[2,2],[3,3]]', '[[1,5],[10,4],[4,3]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWeakCharacters(self, properties: List[List[int]]) -> int:\n",
    "        # properties.sort(key = lambda x:( x[0]*(-1), x[1]))\n",
    "        properties = sorted(properties,key=lambda x:[-x[0],x[1]], reverse=False)\n",
    "        print(properties)\n",
    "        \n",
    "        res = 0\n",
    "        max_def = properties[0][1]\n",
    "        for i in properties[1:]:\n",
    "            if i[1] < max_def:\n",
    "                res += 1\n",
    "            else:\n",
    "                max_def = i[1]\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWeakCharacters(self, properties: List[List[int]]) -> int:\n",
    "        properties.sort(key=lambda x: (-x[0], x[1]))\n",
    "        print(properties)\n",
    "        ans = 0\n",
    "        maxDef = 0\n",
    "        for _, def_ in properties:\n",
    "            if maxDef > def_:\n",
    "                ans += 1\n",
    "            else:\n",
    "                maxDef = max(maxDef, def_)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWeakCharacters(self, properties: List[List[int]]) -> int:\n",
    "        max_atta = max([v[0] for v in properties])\n",
    "        atss = [[] for i in range(max_atta + 1)]\n",
    "        for a,d in properties:\n",
    "            atss[a].append(d)\n",
    "        max_d = 0\n",
    "        res = 0\n",
    "        for i in range(len(atss) - 1, -1, -1):\n",
    "            v = atss[i]\n",
    "            max_val = max_d\n",
    "            for k in v:\n",
    "                if k < max_d:\n",
    "                    res += 1\n",
    "                max_val = max(k, max_val)\n",
    "            max_d = max(max_d, max_val)\n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWeakCharacters(self, properties: List[List[int]]) -> int:\n",
    "        properties.sort(key=lambda x: (x[0], x[1]))\n",
    "        num = []\n",
    "        heapq.heapify(num)\n",
    "        ans = 0\n",
    "        stack = []\n",
    "        res = set()\n",
    "        for per in properties:\n",
    "            if per[0] not in res:\n",
    "                for i in stack:\n",
    "                    heapq.heappush(num, i)\n",
    "                stack = [per[1]]\n",
    "            else:\n",
    "                stack.append((per[1]))\n",
    "            res.add(per[0])\n",
    "            while num:\n",
    "                temp = heapq.heappop(num)\n",
    "                if temp < per[1]:\n",
    "                    ans += 1\n",
    "                else:\n",
    "                    heapq.heappush(num, temp)\n",
    "                    break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWeakCharacters(self, arr: List[List[int]]) -> int:\n",
    "        arr = sorted(arr, key=lambda x : (-x[0], x[1]))\n",
    "        mx = 0\n",
    "        ans = 0\n",
    "        for x, y in arr:\n",
    "            if y < mx: ans += 1\n",
    "            else: mx = y\n",
    "        return ans\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWeakCharacters(self, properties: List[List[int]]) -> int:\n",
    "        num = 0\n",
    "        MaxDef = 0\n",
    "        properties.sort(key = lambda x : (-x[0],x[1]))\n",
    "        for _ , defence in properties:\n",
    "            if defence < MaxDef:\n",
    "                num += 1\n",
    "            else:\n",
    "                 MaxDef = max(MaxDef,defence)\n",
    "        \n",
    "        return num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWeakCharacters(self, properties: List[List[int]]) -> int:\n",
    "        properties.sort(key = lambda x: (-x[0], x[1]))\n",
    "\n",
    "        premax = 0\n",
    "        ans = 0\n",
    "        for x, y in properties:\n",
    "            if premax > y:\n",
    "                ans += 1\n",
    "            premax = max(premax, y)\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWeakCharacters(self, properties: List[List[int]]) -> int:\n",
    "        properties.sort(key=lambda p:(-p[0], p[1]))\n",
    "        ans, max_def = 0, 0\n",
    "        for attack, defense in properties:\n",
    "            if defense < max_def:\n",
    "                ans += 1\n",
    "            else:\n",
    "                max_def = defense\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWeakCharacters(self, properties: List[List[int]]) -> int:\n",
    "        properties.sort(key = lambda x:(-x[0], x[1]))\n",
    "        ma = float('-inf')\n",
    "        max_ = float('-inf')\n",
    "\n",
    "        ans = 0\n",
    "        for i in range(len(properties)):\n",
    "            a, d = properties[i]\n",
    "\n",
    "            if i - 1 >= 0 and d < properties[i - 1][1]:\n",
    "                ma = max_\n",
    "\n",
    "            if ma > d:\n",
    "                ans += 1\n",
    "            \n",
    "            max_ = max(max_, d)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWeakCharacters(self, properties: List[List[int]]) -> int:\n",
    "        # 双排序+一次遍历\n",
    "        properties.sort(key=lambda p: (-p[0], p[1]))  # 攻击降序，攻击相同的防御升序\n",
    "        ans = max_def = 0\n",
    "        for _, d in properties:\n",
    "            if d < max_def: ans += 1  # 因同阶内防御升序，因此只需比防御即可\n",
    "            else: max_def = d\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWeakCharacters(self, properties: List[List[int]]) -> int:\n",
    "        properties.sort(key = lambda x:(-x[0],x[1]))\n",
    "        max_d = 0\n",
    "        ans = 0\n",
    "        for _,d in properties:\n",
    "            if d < max_d:\n",
    "                ans += 1\n",
    "            else:\n",
    "                max_d = d\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWeakCharacters(self, properties: List[List[int]]) -> int:\n",
    "        s = sorted(properties, key=lambda x: x[0], reverse=True)\n",
    "        ans, max_def_comp, max_def = 0, 0, 0\n",
    "        for i in range(1, len(s)):\n",
    "            max_def = max(max_def, s[i - 1][1])\n",
    "            if s[i][0] < s[i - 1][0]:\n",
    "                max_def_comp = max_def\n",
    "            if s[i][1] < max_def_comp:\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWeakCharacters(self, properties: List[List[int]]) -> int:\n",
    "        properties.sort(key=lambda x: (-x[0], x[1]))\n",
    "        ans, max_def = 0, 0\n",
    "        for _, _def in properties:\n",
    "            if max_def > _def:\n",
    "                ans += 1\n",
    "            else:\n",
    "                max_def = max(max_def, _def)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWeakCharacters(self, properties: List[List[int]]) -> int:\n",
    "        properties.sort(key = lambda p:(-p[0], p[1]))\n",
    "        ans = maxDef = 0\n",
    "        for _, d in properties:\n",
    "            if d < maxDef:\n",
    "                ans += 1\n",
    "            else:\n",
    "                maxDef = d \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWeakCharacters(self, properties: List[List[int]]) -> int:\n",
    "        properties.sort(key=lambda p: (-p[0], p[1]))\n",
    "        ans = max_def = 0\n",
    "        for _, d in properties:\n",
    "            if d < max_def: ans += 1\n",
    "            else: max_def = d\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWeakCharacters(self, properties: List[List[int]]) -> int:\n",
    "        properties.sort(key=lambda x:(-x[0],x[1]))\n",
    "        ans=0\n",
    "        maxdef=0\n",
    "        for _,def_ in properties:\n",
    "            if maxdef>def_:\n",
    "                ans+=1\n",
    "            else:\n",
    "                maxdef=def_\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWeakCharacters(self, properties: List[List[int]]) -> int:\n",
    "        # 强吃弱难，弱被吃易\n",
    "        # 重点：排序\n",
    "        properties.sort(key=lambda x: (-x[0], x[1]))\n",
    "        ans = maxi = 0\n",
    "        for _, d in properties:\n",
    "            if d < maxi:\n",
    "                ans += 1\n",
    "            else:\n",
    "                maxi = d\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWeakCharacters(self, properties: List[List[int]]) -> int:\n",
    "        n = len(properties)\n",
    "        properties = sorted(properties,key = lambda x:(-x[0],x[1]))\n",
    "\n",
    "        max_def = 0\n",
    "        res = 0\n",
    "        for attack,_def in properties:\n",
    "            if (_def<max_def):\n",
    "                res += 1\n",
    "            else:\n",
    "                max_def = _def\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWeakCharacters(self, properties: List[List[int]]) -> int:\n",
    "        properties.sort(key=lambda x: (-x[0], x[1]))\n",
    "        ans = 0\n",
    "        maxDef = 0\n",
    "        for _, def_ in properties:\n",
    "            if maxDef > def_:\n",
    "                ans += 1\n",
    "            else:\n",
    "                maxDef = max(maxDef, def_)\n",
    "        return ans\n",
    "        # num=0\n",
    "        # if len(properties)==1:\n",
    "        #     return num\n",
    "        # keys=sorted(range(len(properties)),key=lambda i:properties[i][0])\n",
    "        # B=sorted(range(1,len(properties)),key=lambda i:(-properties[keys[i]][1],-properties[keys[i]][0]))\n",
    "        # j=B[0]\n",
    "        # print(keys,B,j)\n",
    "        # for i in range(len(keys)):\n",
    "        #     if i<j:\n",
    "        #         print('ij',i,j)\n",
    "        #         if properties[keys[i]][1]<properties[keys[j]][1] and properties[keys[i]][0]<properties[keys[j]][0]:\n",
    "        #             print('yes',i,j)\n",
    "        #             num+=1\n",
    "        #         continue\n",
    "        #     else:\n",
    "        #         if i==len(properties)-1:\n",
    "        #             break\n",
    "        #         j=i+1\n",
    "        #         while j<len(properties)-1 and properties[keys[j]][0]==properties[keys[i]][0]:\n",
    "        #             j+=1\n",
    "        #         B=sorted(range(j,len(properties)),key=lambda x:(-properties[keys[x]][1],properties[keys[x]][0]))#B=sorted(keys[i+1:],key=lambda x:-properties[x][1])\n",
    "        #         j=B[0]\n",
    "        # return num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWeakCharacters(self, properties: List[List[int]]) -> int:\n",
    "        properties.sort(key = lambda x: (-x[0], x[1]))\n",
    "\n",
    "        ans = 0\n",
    "        prey = 0\n",
    "\n",
    "        for _, y in properties:\n",
    "            if prey > y:\n",
    "                ans += 1\n",
    "            prey = max(prey, y)\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWeakCharacters(self, properties: List[List[int]]) -> int:\n",
    "        properties.sort(key = lambda x:(-x[0],x[1]))\n",
    "        maxdef = 0\n",
    "        ans = 0\n",
    "        for g,f in properties:\n",
    "            if maxdef>f:\n",
    "                ans += 1\n",
    "            else:\n",
    "                maxdef = max(maxdef,f)\n",
    "        return ans\n",
    "\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWeakCharacters(self, properties: List[List[int]]) -> int:\n",
    "        # properties.sort(key=lambda x: (x[0], x[1]))\n",
    "        # num = []\n",
    "        # heapq.heapify(num)\n",
    "        # ans = 0\n",
    "        # stack = []\n",
    "        # res = set()\n",
    "        # for per in properties:\n",
    "        #     if per[0] not in res:\n",
    "        #         for i in stack:\n",
    "        #             heapq.heappush(num, i)\n",
    "        #         stack = [per[1]]\n",
    "        #     else:\n",
    "        #         stack.append((per[1]))\n",
    "        #     res.add(per[0])\n",
    "        #     while num:\n",
    "        #         temp = heapq.heappop(num)\n",
    "        #         if temp < per[1]:\n",
    "        #             ans += 1\n",
    "        #         else:\n",
    "        #             heapq.heappush(num, temp)\n",
    "        #             break\n",
    "        # return ans\n",
    "\n",
    "        properties.sort(key = lambda x: (x[0], -x[1]))\n",
    "        ans = 0\n",
    "        st = []\n",
    "        for _, def_ in properties:\n",
    "            while st and st[-1] < def_:\n",
    "                st.pop()\n",
    "                ans += 1\n",
    "            st.append(def_)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWeakCharacters(self, properties: List[List[int]]) -> int:\n",
    "        properties.sort(key=lambda x : (-x[0], x[1]))\n",
    "        ans = 0\n",
    "        maxDef = properties[0][1]\n",
    "        for property in properties:\n",
    "            if property[1] < maxDef:\n",
    "                ans += 1\n",
    "            else:\n",
    "                maxDef = property[1]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWeakCharacters(self, properties: List[List[int]]) -> int:\n",
    "        '''\n",
    "        按照攻击值降序排列，则前面的攻击值高于后面的；\n",
    "        攻击值相同时，防御值升序排列；遍历过程中，维护前面的最大防御值；\n",
    "        如果当前防御值小于最大值，则当前为弱角色；否则，则更新最大值。       \n",
    "        '''\n",
    "        properties.sort(key=lambda p:(-p[0], p[1]))\n",
    "        ans, max_def = 0, 0\n",
    "        for attack, defense in properties:\n",
    "            if defense < max_def:\n",
    "                ans += 1\n",
    "            else:\n",
    "                max_def = defense\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWeakCharacters(self, properties: List[List[int]]) -> int:\n",
    "        n = len(properties)\n",
    "        properties.sort(key=lambda x:(x[0],x[1]))\n",
    "        res = 0\n",
    "        cur_atk = properties[-1][0]\n",
    "        old_max_defen = -1\n",
    "        cur_max_defen = properties[-1][1]\n",
    "        for i in range(n-2, -1, -1):\n",
    "            atk, defen = properties[i]\n",
    "            if atk == cur_atk:\n",
    "                cur_max_defen = max(defen, cur_max_defen)\n",
    "                if defen<old_max_defen:\n",
    "                    res+=1\n",
    "            else:\n",
    "                old_max_defen = cur_max_defen\n",
    "                if defen<old_max_defen:\n",
    "                    res+=1\n",
    "                cur_max_defen = max(defen, cur_max_defen)\n",
    "                cur_atk = atk\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWeakCharacters(self, properties: List[List[int]]) -> int:\n",
    "        properties.sort(key = lambda x: (x[0], -x[1]))\n",
    "        ans = 0\n",
    "        f = []\n",
    "        pre_atk = 0\n",
    "        for atk, d in properties:\n",
    "            if atk > pre_atk:\n",
    "                if f and d > f[-1]:\n",
    "                    i = bisect.bisect(f, -d, key = lambda x:-x)\n",
    "                    ans += len(f) - i\n",
    "                    del f[i:]\n",
    "                pre_atk = atk\n",
    "            f.append(d)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWeakCharacters(self, properties: List[List[int]]) -> int:\n",
    "        properties.sort(key = lambda x:(-x[0], x[1]))\n",
    "        n = len(properties)\n",
    "        result = 0\n",
    "        maxd = 0\n",
    "        for a, d in properties:\n",
    "            if(d < maxd):\n",
    "                result += 1\n",
    "            else:\n",
    "                maxd = d\n",
    "        return result\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWeakCharacters(self, properties: List[List[int]]) -> int:\n",
    "        properties.sort(key=lambda p: (-p[0], p[1]))\n",
    "        ans = max_def = 0\n",
    "        for _, d in properties:\n",
    "            if d < max_def: ans += 1\n",
    "            else: max_def = d\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWeakCharacters(self, properties: List[List[int]]) -> int:\n",
    "        properties.sort(key = lambda x: (x[0], -x[1]))\n",
    "        ans = 0\n",
    "        f = []\n",
    "        for atk, d in properties:\n",
    "            if f and d > f[-1]:\n",
    "                i = bisect.bisect(f, -d, key = lambda x:-x)\n",
    "                ans += len(f) - i\n",
    "                del f[i:]\n",
    "            f.append(d)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWeakCharacters(self, properties: List[List[int]]) -> int:\n",
    "        properties.sort(key=lambda p:(-p[0], p[1]))\n",
    "        ans = max_def = 0\n",
    "\n",
    "        for _, d in properties:\n",
    "            if d < max_def:\n",
    "                ans += 1\n",
    "            else:\n",
    "                max_def = d\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWeakCharacters(self, properties: List[List[int]]) -> int:\n",
    "        # 按照 attack 排序，如果 attack 相同，按照 defense 递减排序\n",
    "        properties.sort(key=lambda x: (x[0], -x[1]))\n",
    "        \n",
    "        weak_count = 0\n",
    "        max_defense = 0  # 记录已遍历过的角色中具有最大 defense 值的角色\n",
    "        \n",
    "        # 从右到左遍历排序后的 properties\n",
    "        for _, defense in reversed(properties):\n",
    "            # 检查当前角色是否是弱角色\n",
    "            if defense < max_defense:\n",
    "                weak_count += 1\n",
    "            else:\n",
    "                max_defense = defense  # 更新 max_defense\n",
    "\n",
    "        return weak_count\n",
    "\n",
    "# 测试代码\n",
    "s = Solution()\n",
    "print(s.numberOfWeakCharacters([[5, 5], [6, 3], [3, 6]]))  # 输出 0\n",
    "print(s.numberOfWeakCharacters([[2, 2], [3, 3]]))  # 输出 1\n",
    "print(s.numberOfWeakCharacters([[1, 5], [10, 4], [4, 3]]))  # 输出 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWeakCharacters(self, properties: List[List[int]]) -> int:\n",
    "        # properties.sort(key=lambda x: (x[0], x[1]))\n",
    "        # num = []\n",
    "        # heapq.heapify(num)\n",
    "        # ans = 0\n",
    "        # stack = []\n",
    "        # res = set()\n",
    "        # for per in properties:\n",
    "        #     if per[0] not in res:\n",
    "        #         for i in stack:\n",
    "        #             heapq.heappush(num, i)\n",
    "        #         stack = [per[1]]\n",
    "        #     else:\n",
    "        #         stack.append((per[1]))\n",
    "        #     res.add(per[0])\n",
    "        #     while num:\n",
    "        #         temp = heapq.heappop(num)\n",
    "        #         if temp < per[1]:\n",
    "        #             ans += 1\n",
    "        #         else:\n",
    "        #             heapq.heappush(num, temp)\n",
    "        #             break\n",
    "        # return ans\n",
    "\n",
    "        properties.sort(key= lambda x:(-x[0],x[1]))\n",
    "        ans = 0\n",
    "        maxnum = 0\n",
    "        for idx,num in properties:\n",
    "            if num < maxnum:\n",
    "                ans += 1\n",
    "            else:\n",
    "                maxnum = num\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWeakCharacters(self, properties: List[List[int]]) -> int:\n",
    "        #这道题解法的精髓在于\n",
    "        #用排序让某一个元素不用比较\n",
    "        #用一个变量让另一个元素只需维护一个值就能比较\n",
    "        #我们让attack由大到小排列\n",
    "        #这样的话这样的话需要维护defense，如果defense小于max_def可能要遭殃\n",
    "        #让我再来详细盘一下这个逻辑\n",
    "        #让def由小到大排列，是为了让相同的attack不至于被选出来\n",
    "\n",
    "        #这道题其实挺难的，如果换成attck1 >= attack2 ,有等于，有不等于该怎么办\n",
    "        #这次算是自己想出来了\n",
    "        n = len(properties)\n",
    "        properties = sorted(properties,key = lambda x:(-x[0],x[1]))\n",
    "        max_def = properties[0][1]\n",
    "        ans = 0\n",
    "        for i in range(1,n,1):\n",
    "            attack,defense = properties[i]\n",
    "            if ( defense < max_def):\n",
    "                ans += 1\n",
    "            max_def = max(max_def,defense)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWeakCharacters(self, properties: List[List[int]]) -> int:\n",
    "        properties.sort(key=lambda p: (-p[0], p[1]))\n",
    "        ans = max_def = 0\n",
    "        for _, d in properties:\n",
    "            if d < max_def: ans += 1\n",
    "            else: max_def = d\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWeakCharacters(self, properties: List[List[int]]) -> int:\n",
    "        properties.sort(key = lambda x: (-x[0], x[1]))\n",
    "        res = max_def = 0\n",
    "        for _, x in properties:\n",
    "            if x < max_def:\n",
    "                res += 1\n",
    "            else:\n",
    "                max_def = x\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWeakCharacters(self, properties: List[List[int]]) -> int:\n",
    "        # 先排序，能够确定一个维度的大小顺序。从后往前遍历，后面的\n",
    "        # 攻击力肯定比当前的大（或者等于），再去维护防御的最大值\n",
    "        # 需要注意的是，需要维护两个防御的最大值，一个是之前的（不包含当前攻击力的），\n",
    "        # 一个是之前的与当前攻击力的最大防御值。\n",
    "        n = len(properties)\n",
    "        properties.sort(key=lambda x:(x[0],x[1]))\n",
    "        res = 0\n",
    "        cur_atk = properties[-1][0]\n",
    "        old_max_defen = -1\n",
    "        cur_max_defen = properties[-1][1]\n",
    "        for i in range(n-2, -1, -1):\n",
    "            atk, defen = properties[i]\n",
    "            if atk == cur_atk:\n",
    "                cur_max_defen = max(defen, cur_max_defen)\n",
    "                if defen<old_max_defen:\n",
    "                    res+=1\n",
    "            else:\n",
    "                old_max_defen = cur_max_defen\n",
    "                if defen<old_max_defen:\n",
    "                    res+=1\n",
    "                cur_max_defen = max(defen, cur_max_defen)\n",
    "                cur_atk = atk\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWeakCharacters(self, properties: List[List[int]]) -> int:\n",
    "        properties.sort(key=lambda x:(-x[0], x[1]))\n",
    "        ret = maxv = 0\n",
    "        for x, y in properties:\n",
    "            ret += y < maxv\n",
    "            maxv = max(maxv, y)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWeakCharacters(self, properties: List[List[int]]) -> int:\n",
    "        properties.sort(key = lambda x: (x[0], -x[1])) # 按照数组的第一位排序\n",
    "        stk=[]\n",
    "        cnt=0\n",
    "        for A,B in properties:\n",
    "            while stk and stk[-1]<B:\n",
    "                cnt+=1\n",
    "                stk.pop()\n",
    "            stk.append(B)\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWeakCharacters(self, properties: List[List[int]]) -> int:\n",
    "        properties.sort(key=lambda x:(-x[0], x[1]))\n",
    "        maxs = 0\n",
    "        res = 0\n",
    "        for i in range(len(properties)):\n",
    "            a, d = properties[i]\n",
    "            if d < maxs:\n",
    "                res += 1\n",
    "            maxs = max(maxs, d)\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "def cmp(x, y):\n",
    "    if x[0] != y[0]:\n",
    "        return x[0] - y[0]\n",
    "    \n",
    "    return y[1] - x[1]\n",
    "\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def numberOfWeakCharacters(self, properties: List[List[int]]) -> int:\n",
    "        properties.sort(key=cmp_to_key(cmp))\n",
    "        n = len(properties)\n",
    "        maxdefense = 0\n",
    "        ans = 0\n",
    "        for i in range(n-1,-1,-1):\n",
    "            if properties[i][1] < maxdefense:\n",
    "                ans += 1\n",
    "            maxdefense = max(maxdefense, properties[i][1])\n",
    "        return ans\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWeakCharacters(self, properties: List[List[int]]) -> int:\n",
    "        properties.sort(key = lambda x: (x[0], -x[1])) # 按照数组的第一位排序\n",
    "        print(properties)\n",
    "        stk=[]\n",
    "        cnt=0\n",
    "        for A,B in properties:\n",
    "            while stk and stk[-1]<B:\n",
    "                cnt+=1\n",
    "                stk.pop()\n",
    "            stk.append(B)\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWeakCharacters(self, properties: List[List[int]]) -> int:\n",
    "        # 只要找到一个AD都绝对更大的，就判定是weak的情况\n",
    "        n = len(properties)\n",
    "        stack = []\n",
    "        cnt = 0\n",
    "        # [5,3], [5,5], [3,1], [3,3], [1,1],[1,2]\n",
    "        properties.sort(key = lambda x: (-x[0], x[1]))\n",
    "        # 防御最大值\n",
    "        defMax = properties[0][1]\n",
    "        for i in range(1, n):\n",
    "            if properties[i][1] < defMax:\n",
    "                cnt += 1\n",
    "                continue\n",
    "            if defMax < properties[i][1]:\n",
    "                defMax = properties[i][1]\n",
    "        return cnt\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWeakCharacters(self, properties: List[List[int]]) -> int:\n",
    "        properties.sort(reverse=True)\n",
    "        n = len(properties)\n",
    "        i = 1\n",
    "        maxb = -1\n",
    "        cur_maxb = properties[0][1]\n",
    "        ans = 0\n",
    "        while i < n:\n",
    "            if properties[i][0] != properties[i-1][0]:\n",
    "                maxb = max(maxb, cur_maxb)\n",
    "                cur_maxb = properties[i][1]\n",
    "                if properties[i][1] < maxb:\n",
    "                    ans += 1\n",
    "            else:\n",
    "                if properties[i][1] < maxb:\n",
    "                    ans += 1\n",
    "            i += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWeakCharacters(self, properties: List[List[int]]) -> int:\n",
    "        properties.sort(key=lambda x:(x[0],-x[1]))\n",
    "\n",
    "        stack = []\n",
    "        ans=0\n",
    "        for _,attack in properties:\n",
    "            while stack and stack[-1]<attack:\n",
    "                ans+=1\n",
    "                stack.pop()\n",
    "            stack.append(attack)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWeakCharacters(self, properties: List[List[int]]) -> int:\n",
    "        properties.sort(reverse=True)\n",
    "        lastx = maxv = 0\n",
    "        ret = 0\n",
    "        for x, y in properties:\n",
    "            if x != lastx:\n",
    "                lastmaxv = maxv\n",
    "            ret += y < lastmaxv\n",
    "            maxv = max(maxv, y)\n",
    "            lastx = x\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "def cmp(x, y):\n",
    "    if x[0] != y[0]:\n",
    "        return x[0] - y[0]\n",
    "    \n",
    "    return y[1] - x[1]\n",
    "\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def numberOfWeakCharacters(self, properties: List[List[int]]) -> int:\n",
    "\n",
    "        '''\n",
    "        第一个数升序排列\n",
    "        第二个数降序排列\n",
    "        倒着遍历properties, 对于i来说, attack[i] >= attack[j] j < i\n",
    "        因此, 如果右边有玩家的防御大于i的防御, 那么i就比他弱\n",
    "        '''\n",
    "\n",
    "        # 第一个数升序排列\n",
    "        # 第二个数降序排列\n",
    "        properties.sort(key=cmp_to_key(cmp))\n",
    "        n = len(properties)\n",
    "        maxdefense = 0\n",
    "        ans = 0\n",
    "        for i in range(n-1,-1,-1):\n",
    "            if properties[i][1] < maxdefense:\n",
    "                ans += 1\n",
    "            maxdefense = max(maxdefense, properties[i][1])\n",
    "        return ans\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWeakCharacters(self, properties: List[List[int]]) -> int:\n",
    "        '''\n",
    "        按照攻击值降序排列，则前面的攻击值高于后面的；\n",
    "        攻击值相同时，防御值升序排列；遍历过程中，维护前面的最大防御值；\n",
    "        如果当前防御值小于最大值，则当前为弱角色；否则，则更新最大值。       \n",
    "        '''\n",
    "        properties.sort(key=lambda p:(-p[0], p[1]))\n",
    "        ans, max_def = 0, 0\n",
    "        for attack, defense in properties:\n",
    "            if defense < max_def:\n",
    "                ans += 1\n",
    "            else:\n",
    "                max_def = defense\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWeakCharacters(self, properties: List[List[int]]) -> int:\n",
    "        n=len(properties)\n",
    "        ans=0\n",
    "        properties.sort(key=lambda x:(x[0],-x[1]))\n",
    "        maxx=-inf\n",
    "        for i in range(n-1,-1,-1):\n",
    "            if properties[i][1]<maxx:\n",
    "                ans+=1\n",
    "            maxx=max(maxx,properties[i][1])\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWeakCharacters(self, properties: List[List[int]]) -> int:\n",
    "        properties.sort(key = lambda p: (-p[0], p[1]))\n",
    "        ans = maxD = 0\n",
    "        for _, d in properties:\n",
    "            if d < maxD:\n",
    "                ans += 1\n",
    "            else:\n",
    "                maxD = d\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWeakCharacters(self, properties: List[List[int]]) -> int:\n",
    "        properties.sort(key = lambda x: (-x[0], x[1]))  # 攻击力从大到小  防御力从小到大\n",
    "        res = max_def = 0\n",
    "        for _, x in properties:\n",
    "            if x < max_def:\n",
    "                res += 1\n",
    "            else:\n",
    "                max_def = x\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWeakCharacters(self, properties: List[List[int]]) -> int:\n",
    "        properties.sort(key=lambda p: (-p[0], p[1]))\n",
    "        ans = 0\n",
    "        mx = 0\n",
    "        for a, b in properties:\n",
    "            if b < mx: ans += 1\n",
    "            else: mx = b\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWeakCharacters(self, properties: List[List[int]]) -> int:\n",
    "        properties.sort(key = lambda x: (x[0], -x[1])) # 按照数组的第一位排序\n",
    "        stk=[]\n",
    "        cnt=0\n",
    "        for A,B in properties:\n",
    "            while stk and stk[-1]<B:\n",
    "                cnt+=1\n",
    "                stk.pop()\n",
    "            stk.append(B)\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWeakCharacters(self, nums: List[List[int]]) -> int:\n",
    "        nums.sort(key=lambda x:(x[0],-x[1]))\n",
    "        ans=0\n",
    "        stk=[]\n",
    "        for i,j in nums:\n",
    "            if not stk or stk[-1][1]>=j:\n",
    "                stk.append([i,j])\n",
    "            else:\n",
    "                while stk and stk[-1][0]<i and stk[-1][1]<j:\n",
    "                    ans+=1\n",
    "                    stk.pop()\n",
    "                stk.append([i,j])\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def numberOfWeakCharacters(self, properties: List[List[int]]) -> int:\n",
    "\n",
    "        '''\n",
    "        第一个数升序排列\n",
    "        第二个数降序排列\n",
    "        倒着遍历properties, 对于i来说, attack[i] >= attack[j] j < i\n",
    "        因此, 如果右边有玩家的防御大于i的防御, 那么i就比他弱\n",
    "        '''\n",
    "\n",
    "        # 第一个数升序排列\n",
    "        # 第二个数降序排列\n",
    "        properties.sort(key=lambda x: (x[0], -x[1]))\n",
    "        n = len(properties)\n",
    "        maxdefense = 0\n",
    "        ans = 0\n",
    "        for i in range(n-1,-1,-1):\n",
    "            if properties[i][1] < maxdefense:\n",
    "                ans += 1\n",
    "            maxdefense = max(maxdefense, properties[i][1])\n",
    "        return ans\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWeakCharacters(self, properties: List[List[int]]) -> int:\n",
    "        properties.sort(key=lambda x:(x[0],-x[-1]))\n",
    "        st = []\n",
    "        ans = 0\n",
    "        for x,y in properties:\n",
    "            while st and st[-1] < y:\n",
    "                st.pop()\n",
    "                ans += 1\n",
    "            st.append(y)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWeakCharacters(self, properties: List[List[int]]) -> int:\n",
    "        n = len(properties)\n",
    "        stk = []\n",
    "        res = 0\n",
    "\n",
    "        def cmp(a: tuple):\n",
    "            return a[0], -a[1]\n",
    "\n",
    "        properties.sort(key=cmp)\n",
    "\n",
    "        for i in range(n):\n",
    "            while stk and properties[stk[-1]][1] < properties[i][1]:\n",
    "                stk.pop()\n",
    "                res += 1\n",
    "            stk.append(i)\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\r\n",
    "class Solution:\r\n",
    "    def numberOfWeakCharacters(self, properties: List[List[int]]) -> int:\r\n",
    "        # 有序集合过了，但是好慢,等等看下题解区，休息下\r\n",
    "        properties.sort(key=lambda x:[x[0], -x[1]])\r\n",
    "        res = 0 \r\n",
    "        mx = properties[-1][1]\r\n",
    "        for i in range(len(properties) - 2, -1, -1):\r\n",
    "            if properties[i][1] < mx:\r\n",
    "                res += 1\r\n",
    "            else:\r\n",
    "                mx = properties[i][1] \r\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWeakCharacters(self, properties: List[List[int]]) -> int:\n",
    "        properties.sort(key=lambda x: (x[0],-x[1]))\n",
    "        res = 0\n",
    "        stack = []\n",
    "        for _, d in properties:\n",
    "            while stack and stack[-1] < d:\n",
    "                stack.pop()\n",
    "                res += 1\n",
    "            stack.append(d)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\r\n",
    "class Solution:\r\n",
    "    def numberOfWeakCharacters(self, properties: List[List[int]]) -> int:\r\n",
    "        # 有序集合过了，但是好慢,等等看下题解区，休息下\r\n",
    "        properties.sort(key=lambda x:[x[0], -x[1]])\r\n",
    "        # sl = SortedList()\r\n",
    "        res = 0 \r\n",
    "        mx = -inf\r\n",
    "        for x, y in properties[::-1]:\r\n",
    "            if y < mx:\r\n",
    "                res += 1\r\n",
    "            else:\r\n",
    "                mx = y \r\n",
    "        \r\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWeakCharacters(self, arr: List[List[int]]) -> int:\n",
    "        xs = [x[0] for x in arr]\n",
    "        xs = sorted(list(set(xs)), reverse=True)\n",
    "        ys = defaultdict(list) \n",
    "        for x, y in arr:\n",
    "            ys[x].append(y)\n",
    "        mx = 0\n",
    "        ans = 0\n",
    "        for x in xs:\n",
    "            for y in ys[x]:\n",
    "                if y < mx: ans += 1\n",
    "            mx = max(mx, max(ys[x]))\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWeakCharacters(self, arr: List[List[int]]) -> int:\n",
    "        xs = [x[0] for x in arr]\n",
    "        xs = sorted(list(set(xs)), reverse=True)\n",
    "        ys = defaultdict(list) \n",
    "        for x, y in arr:\n",
    "            ys[x].append(y)\n",
    "        mx = 0\n",
    "        ans = 0\n",
    "        for x in xs:\n",
    "            for y in ys[x]:\n",
    "                if y < mx: ans += 1\n",
    "            mx = max(mx, max(ys[x]))\n",
    "        return ans\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWeakCharacters(self, properties: List[List[int]]) -> int:\n",
    "        properties = sorted(properties,key = lambda lis:[-lis[0],lis[1]])\n",
    "        count=0\n",
    "        MaxY=0\n",
    "        for x , y in properties:\n",
    "            if y < MaxY:\n",
    "                count = count + 1\n",
    "            else:\n",
    "                MaxY = y\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWeakCharacters(self, properties: List[List[int]]) -> int:\n",
    "        properties.sort(key = lambda x: (x[0], -x[1]))\n",
    "        stack = []\n",
    "        ans = 0\n",
    "        for a, d in properties:\n",
    "            while stack and stack[-1][0] < a and stack[-1][1] < d:\n",
    "                stack.pop()\n",
    "                ans += 1\n",
    "            stack.append((a, d))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWeakCharacters(self, properties: List[List[int]]) -> int:\n",
    "        # 在保证一个属性有效有序的前提下取分析另外一个属性\n",
    "        ans = 0\n",
    "        n = len(properties)\n",
    "        properties.sort()\n",
    "        a = [x for x, y in properties]\n",
    "        d = [y for x, y in properties]\n",
    "        \n",
    "        dp = [y for x, y in properties]\n",
    "        for i in range(n-2, -1, -1):\n",
    "            dp[i] = max(dp[i], dp[i+1])\n",
    "        \n",
    "        for i in range(n):\n",
    "            x = a[i]\n",
    "            y = d[i]\n",
    "            j = bisect_right(a, x)\n",
    "            if j < n:\n",
    "                ans += int(dp[j] > y)\n",
    "        \n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "class Solution:\n",
    "    def numberOfWeakCharacters(self, properties: List[List[int]]) -> int:\n",
    "        n = len(properties)\n",
    "        properties.sort(key=lambda x: -x[0])\n",
    "        max_d = [0]*n\n",
    "        for i in range(n):\n",
    "            max_d[i] = max(max_d[i-1], properties[i][1])\n",
    "\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            x, y = 0, n-1\n",
    "            while x < y:\n",
    "                z = (x+y)//2\n",
    "                if properties[z][0] <= properties[i][0]:\n",
    "                    y = z\n",
    "                else:\n",
    "                    x = z+1\n",
    "            if x > 0 and max_d[x-1] > properties[i][1]:\n",
    "                ans += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWeakCharacters(self, properties: List[List[int]]) -> int:\n",
    "        properties.sort(key = lambda x: (x[0], -x[1]))\n",
    "        stack = []\n",
    "        ans = 0\n",
    "        for a, d in properties:\n",
    "            while stack and stack[-1][0] < a and stack[-1][1] < d:\n",
    "                stack.pop()\n",
    "                ans += 1\n",
    "            stack.append((a, d))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWeakCharacters(self, properties: List[List[int]]) -> int:\n",
    "        properties.sort(key=lambda x: (x[0], -x[1]))\n",
    "        stack = []\n",
    "        ans = 0\n",
    "        for a, d in properties:\n",
    "            while stack and stack[-1][0] < a and stack[-1][1] < d:\n",
    "                stack.pop()\n",
    "                ans += 1\n",
    "            stack.append((a, d))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def numberOfWeakCharacters(self, properties: List[List[int]]) -> int:\n",
    "        sl = SortedList()\n",
    "\n",
    "        mp = collections.defaultdict(list)\n",
    "\n",
    "        for a,d in properties:\n",
    "            mp[a].append(d)\n",
    "            sl.add(d)\n",
    "        \n",
    "        kk = sorted(mp.keys())\n",
    "\n",
    "        ans = 0\n",
    "\n",
    "        for k in kk:\n",
    "            if k == kk[-1]:\n",
    "                break\n",
    "            \n",
    "            d = mp[k]\n",
    "\n",
    "            for ele in d:\n",
    "                sl.remove(ele)\n",
    "            \n",
    "            max_ = sl[-1]\n",
    "            \n",
    "            for ele in d:\n",
    "                if ele < max_:\n",
    "                    ans += 1\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWeakCharacters(self, properties: List[List[int]]) -> int:\n",
    "        properties.sort(key=lambda x: (x[0], -x[1]))\n",
    "        stack = []\n",
    "        ans = 0\n",
    "        for a, d in properties:\n",
    "            while stack and stack[-1][0] < a and stack[-1][1] < d:\n",
    "                stack.pop()\n",
    "                ans += 1\n",
    "            stack.append((a, d))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWeakCharacters(self, properties: List[List[int]]) -> int:\n",
    "        n = len(properties)\n",
    "        ans = 0\n",
    "        maxStack = []   # monotonic ascending stack, maxStack[-1]: index of character with max defend\n",
    "        # sort properties by attack ascendingly and defend descendingly\n",
    "        properties.sort(key=lambda x: (x[0], -x[1]))\n",
    "        for i, (attack, defend) in enumerate(properties):\n",
    "            while maxStack and properties[maxStack[-1]][1] < defend:\n",
    "                maxStack.pop()\n",
    "                ans += 1    # maxStack[-1] is index of a weak character\n",
    "            maxStack.append(i)\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "           \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWeakCharacters(self, properties: List[List[int]]) -> int:\n",
    "        properties.sort(key=lambda x:(x[0],-x[1]))\n",
    "        stack=[]\n",
    "        n=len(properties)\n",
    "        for i in range (0,n):\n",
    "            while stack and stack[-1][1]<properties[i][1]:\n",
    "                stack.pop()\n",
    "            stack.append(properties[i])\n",
    "        return n-len(stack)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWeakCharacters(self, properties: List[List[int]]) -> int:\n",
    "        n = len(properties)\n",
    "        properties.sort(reverse=True)\n",
    "        ans = 0\n",
    "        pa = 0\n",
    "        dic = defaultdict(int)\n",
    "        ma = 0\n",
    "        for a, d in properties:\n",
    "            if a != pa:\n",
    "                ma = max(ma, dic[pa])\n",
    "                pa = a\n",
    "            if ma > d:\n",
    "                ans += 1\n",
    "            dic[a] = max(dic[a], d)\n",
    "\n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
